package com.company.algo.listnode;


import com.company.algo.pojo.ListNode;

public class ReverseNodes_K_group {
    /** 反转区间 [a, b) 的元素，注意是左闭右开 */
    ListNode reverse(ListNode a, ListNode b) {
        ListNode pre = null;
        ListNode cur = a;
        ListNode nxt = a;
        while (cur!=b){
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }

    /**
     * 1、先反转以 head 开头的 k 个元素
     * 2、将第 k + 1 个元素作为 head 递归调用 reverseKGroup 函数。
     * 3、将上述两个过程的结果连接起来。
     * 题目说了，如果最后的元素不足 k 个，就保持不变。这就是 base case，
     * @param head
     * @param k
     * @return
     */
    ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;
        // 反转前 k 个元素
        ListNode a = head, b = head;
        for (int i = 0; i < k; i++) {
            //不足k个，不需要反转，base case
            if (b == null) return head;
            b = b.next;
        }
        ListNode newHead = reverse(a,b);
        //递归反转后续链表并连接起来
        a.next = reverseKGroup(b,k);
        return newHead;
    }
}
